home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / 031-040 / amok32 / ringbuffers / ringbuffers.dok < prev    next >
Text File  |  1993-11-04  |  8KB  |  199 lines

  1. ======================================================================
  2. Dokumentation zu "RingBuffers" Version 1.2
  3. Autor: Nicolas Benezan, Postwiesenstr. 2, D7000 Stuttgart 60
  4. ======================================================================
  5.  
  6. Übersicht
  7. ­­­­­­­­­
  8. * Kopierrecht
  9. * Umfang des Projekts
  10. * Einleitung
  11. * Beschreibung der Prozeduren
  12. * Demo- / Testprogramm
  13.  
  14.  
  15. Kopierrecht
  16. ­­­­­­­­­­­
  17. Das komplette Projekt (Quelltext, Dokumentation und Objectcode) ist
  18. Public Domain Software. Es darf beliebig kopiert und verbreitet werden
  19. solange...
  20.  
  21. * mein Name und dieser Kopierrechtshinweis erhalten bleiben,
  22. * die Vollständigkeit des ganzen Projekts gewährleistet ist, und
  23. * mit dem Vertrieb dieser Software kein Gewinn erwirtschaftet wird.
  24.  
  25. Die Kommerzielle Nutzung ohne meine ausdrückliche schriftliche
  26. Genehmigung ist untersagt (über Gewinnbeteiligung läßt sich reden).
  27. W i c h t i g: Dies gilt insbesondere auch für "schwarze Schafe" der
  28. "PD"-Versandhäuser, die ganz offensichtlich Gewinn machen, was z.B. durch
  29. ganzseitige Anzeigen in Zeitschiften erkennbar ist.
  30.  
  31. Verbesserungsvorschläge sind stets willkommen. Falls Sie Veränderungen
  32. am Programm vornehmen, dokumentieren Sie diese bitte gut verständlich.
  33. Es würde mich freuen, wenn Sie mich über größere Veränderungen oder
  34. Erweiterungen in Kenntnis setzen würden.
  35.  
  36. (c) 1988 by Nicolas Benezan.
  37.  
  38.  
  39. Umfang des Projekts
  40. ­­­­­­­­­­­­­­­­­­­
  41. Das komplette Projekt "RingBuffers" beinhaltet folgende Dateien:
  42.  
  43. * RingBuffers.dok   Diese Dokumentation
  44. * RingBuffers.def   Quelltext der Definition
  45. * RingBuffers.mod   Quelltext der Implementation
  46. * MultitaskDemo     Demoprogramm für RingBuffers mit parallelen Prozessen
  47. * SyncDemo          Gegenbeispiel ohne RingBuffers
  48. * MultitaskDemo.mod
  49. * SyncDemo.mod      Quelltexte der Demos
  50.  
  51. (Stand 12.Jan.1990)
  52.  
  53.  
  54. Einleitung
  55. ­­­­­­­­­­
  56. Einen Ringpuffer kann man sich als in sich geschlossene Schleife von
  57. Puffern vorstellen (* = voller Puffer, · = leerer Puffer):
  58.  
  59.        Lesezugriff
  60.        |
  61.    · > - > * > * > * > * > *
  62.    ^                       v
  63.    ·                       *
  64.    ^                       v
  65.    · < · < · < · < + < * < *
  66.                    |
  67.                    Schreibzugriff
  68.  
  69. Die Daten werden dabei wie in einer Art Warteschlange, die immer im Kreis
  70. herum läuft, abgelegt. Am einen Ende werden immer Daten hinzugefügt, am
  71. anderen Ende welche weggenommen. Der Ringpuffer kann auch als FIFO-Speicher
  72. (First-In-First-Out) variabler aber endlicher Größe betrachtet werden.
  73. Es gibt zwei Sonderfälle: Alle Puffer sind voll - in diesem Fall ist der
  74. Schreibzugriff blockiert, oder alle Puffer sind leer - dann ist kein
  75. Lesezugriff mehr möglich.
  76.  
  77. Ringpuffer kommen zum Einsatz, wenn bei zwei asynchron ablaufenden
  78. Prozessen, die Ausgaben des einen als Eingabe für den anderen verwendet
  79. werden (Produzent-Konsument-Problem). Der Ringpuffer dient dazu,
  80. kurzzeitige Unterschiede des "Angebots" und der "Nachfrage" auszugleichen.
  81. Die beiden Prozesse können so ungestört parallel ablaufen, ohne ständig auf
  82. den jeweils anderen Prozess warten zu müssen. Lediglich bei den oben
  83. genannten Sonderfällen treten Wartezeiten ein. Sie treten um so häufiger
  84. auf, je schneller ein Prozess im Vergleich zum anderen ist, bzw. je
  85. geringer das Fassungsvermögen des Ringpuffers ist.
  86.  
  87. Eine denkbare Anwendung für Ringpuffer wäre z.B. ein PIPE-Handler.
  88.  
  89.  
  90. Beschreibung der Prozeduren
  91. ­­­­­­­­­­­­­­­­­­­­­­­­­­­
  92.  
  93. CreateRingBuffer
  94. ----------------
  95. dient zum Erzeugen eines Ringpuffers. Als Parameter werden die Anzahl der
  96. Datenblöcke, aus denen sich der Ringpuffer zusammensetzt, und deren Größe
  97. angegeben. Außerdem müssen noch zwei Signale, FullSignal und EmptySignal,
  98. sowie zwei TaskPtr angegeben werden, deren Bedeutung später noch erläutert
  99. wird.
  100.  
  101. DiscardRingBuffer
  102. -----------------
  103. löscht einen Ringpuffer aus dem Speicher.
  104.  
  105. GetEmptyBlock
  106. -------------
  107. gibt die Adresse des nächsten leeren Blocks zurück (der Block, der sich
  108. neben dem vollen Block mit den "jüngsten" Daten befindet), und sperrt ihn
  109. für weitere Zugriffe.
  110.  
  111. GetFullBlock
  112. ------------
  113. gibt die Adresse des nächsten vollen Blocks (der Block mit den
  114. "ältesten" Daten) zurück, und sperrt den Block für weitere Zugriffe.
  115.  
  116. PutFullBlock
  117. ------------
  118. gibt einen beschriebenen ("gefüllten") Block für Lesezugriffe frei.
  119.  
  120. PutEmptyBlock
  121. -------------
  122. gibt einen gelesenen ("geleerten") Block für Schreibzugriffe frei.
  123.  
  124. AllBlocksFull, AllBlocksEmpty
  125. -----------------------------
  126. erlauben das Feststellen der oben genannten Sonderfälle. Eigentlich müßten
  127. die Prozeduren "NoMoreEmptyBlocks" und "NoMoreFullBlocks" heißen. Wenn
  128. AllBlocksFull() = TRUE ist, bedeutet daß nämlich nicht unbedingt, daß
  129. wirklich alle Puffer (Blöcke) voll sind, sondern nur, daß es keine leeren
  130. Puffer mehr gibt. Es ist ja auch möglich, daß ein Block gerade noch
  131. beschrieben wird, also "halb"-voll ist. Wir wollen jedoch keine
  132. Haarspalterei betreiben und einigen uns darauf, daß wenn AllBlocksFull()
  133. = TRUE ist, kein Schreibzugriff mehr möglich ist.
  134.  
  135.  
  136. Behandlung der Sonderfälle
  137. ­­­­­­­­­­­­­­­­­­­­­­­­­­
  138. Man muß natürlich nicht vor jedem GetEmptyBlock() abfragen ob
  139. AllBlocksFull() sind und umgekehrt. Dazu hat GetEmptyBlock() und
  140. GetFullBlock() einen Resultatstyp BOOLEAN, der FALSE wird, wenn die
  141. entsprechende Operation nicht möglich war.
  142. Wenn nun ein Prozess blockiert wird, weil keine vollen oder leeren Puffer
  143. mehr verfügbar sind, woher weiß der Prozess, wann er wieder weitermachen
  144. kann?
  145. Hierzu dienen die Signale, die man von CreateRingBuffer bekommt. Jedes
  146. PutFullBlock() löst ein FullSignal aus, und jedes PutEmptyBlock() löst ein
  147. EmptySignal aus. Zu beachten ist, daß erst auf ein Signal gewartet werden
  148. darf, wenn GetEmpty- oder GetFullBlock() fehlgeschlagen ist, oder wenn
  149. durch AllBlocksFull() bzw. AllBlocksEmpty() die Notwendigkeit des Wartens
  150. festgestellt wurde. Vorher ist der Zustand der Signale undefiniert.
  151.  
  152. FALSCH:
  153.  
  154.   SigSet:= Exec.Wait (FullSignal);
  155.   Ok:= GetFullBlock (Buffer, Block, DataPtr);
  156.  
  157. RICHTIG:
  158.  
  159.   WHILE NOT GetFullBlock (Buffer, Block, DataPtr) DO
  160.     SigSet:= Exec.Wait (FullSignal);
  161.   END;
  162.  
  163. V O R S I C H T !!! Signale sind nur für den Task gültig, in dem sie mit
  164. Exec.AllocSignal() alloziert wurden! D.h. NUR DER Task, der FullSignal
  165. alloziert hat, darf auch auf das Signal warten, und GENAU DIESER Task muß
  166. auch als Parameter "FullSigTask" bei CreateRingBuffer() angegeben werden!!!
  167.  
  168. Zu warnen ist auch vor Deadlock-Situationen, bei denen beide Prozesse
  169. aufeinander warten und nichts mehr geschieht. Prüfen Sie Ihr Programm
  170. sorfältig auf Korrektheit!
  171.  
  172. Für Fortgeschrittene: Zu bemerken ist, daß FullSigTask und EmptySigTask
  173. auch identisch sein können (!). Allerdings darf dann nicht mit Exec.Wait()
  174. gewartet werden (sonst ist die Ausführungszeit unter Umständen nicht
  175. endlich... ). Quasi-parallel ablaufende Prozesse können auch mit Coroutinen
  176. oder Task-Exceptions realisiert werden.
  177.  
  178.  
  179. Demo- / Testprogramm
  180. ­­­­­­­­­­­­­­­­­­­­
  181. Folgende Demoprogramme sind in diesem Projekt enthalten:
  182.  
  183. * SyncDemo:
  184.   Zeigt mit einer Art Balkendiagramm die absolute (schwarz) und relative
  185.   (weiß) Häufigkeit einzelner Zeichen einer Datei an. Diese Demo zeigt nur
  186.   den Unterschied zu den anderen Demos und verwendet weder RingBuffers noch
  187.   parallele Prozesse.
  188.   Deutlich zu sehen ist der ruckartige Aufbau der Grafik, die durch das
  189.   erforderliche Warten auf das Nachladen von Diskette verursacht wird.
  190.   (Starten des Prgs: Click auf SyncDemo, Doppelclick auf bel. File)
  191.  
  192. * MultitaskDemo:
  193.   Erzeugt die gleiche Grafik, aber  unter Zuhilfenahme von RingBuffers und
  194.   parallel laufenden Tasks. Dies ist gleichzeitig ein Demoprogramm für das
  195.   Modul "TaskSupport", das auf dieser Diskette in einem extra Projekt
  196.   gesondert dokumentiert ist.
  197.  
  198.  
  199.